package study.基础.算法.矩阵快速幂;

import java.util.Scanner;

/**
 * 矩阵快速幂
 *
 * @author Tensai
 * 2019/2/22
 */

public class Main {
    final static int Mod = (int) 1e9 + 7;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 1; i <= T; i++) {
            int n = sc.nextInt();

            if (n < 0 || n == 0) {
                System.out.println(0);
            } else if (n == 1) {
                System.out.println(3);
            } else {
                long[][] a = new long[2][1];
                a[0][0] = 0;
                a[1][0] = 1;
                long[][] c = new long[2][2];
                c[0][0] = 1;
                c[0][1] = 2;
                c[1][0] = 1;
                c[1][1] = 1;

                long[][] x;
                x = Multiply_Matrix(Matrix_Ksm(c, n - 1), a);
                long times = (x[0][0] * 2 % Mod + x[1][0] * 3 % Mod) % Mod;
                System.out.println(times);
            }

        }
    }

    public static long[][] Multiply_Matrix(long[][] a, long[][] b) {        //矩阵乘法
        long[][] c = new long[a.length][b[0].length];
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < b[0].length; j++) {
                long temp = 0;
                for (int x = 0; x < b.length; x++) {
                    temp = (temp + ((a[i][x] % Mod) * (b[x][j] % Mod)) % Mod) % Mod;
                }
                c[i][j] = temp;
            }
        }
        return c;
    }

    public static long[][] Matrix_Ksm(long[][] a, int k) {        //矩阵快速幂
        long[][] d = new long[a.length][a[0].length];
        if (k == 1) {
            return a;
        } else if (k == 2) {
            return Multiply_Matrix(a, a);
        } else if (k % 2 == 0) {
            d = Matrix_Ksm(Multiply_Matrix(a, a), k / 2);
            return d;
        } else {
            d = Matrix_Ksm(Multiply_Matrix(a, a), k / 2);
            return Multiply_Matrix(d, a);
        }
    }
}


